package com.qrpcw.datastructures;

import java.util.ArrayList;

class BSTNode{
	BSTNode leftChild;
	BSTNode rightChild;
	BSTNode parent;
	int key;
	public BSTNode(int key){
		this.key = key;
		leftChild = null;
		rightChild = null;
		parent = null;
	}
}

public class BinarySearchTree {
	private BSTNode root;
	public BinarySearchTree() {
		root = null;
	}
	
	public ArrayList<BSTNode> bstNodes = new ArrayList<BSTNode>();

	public void inOrderTreeWalk(BSTNode x){ //x is root of the tree
		if(x != null){
			inOrderTreeWalk(x.leftChild);
			System.out.print(x.key + " ");
			inOrderTreeWalk(x.rightChild);
		}
	}
	
	public BSTNode treeSerch(BSTNode x, int k){
		if(x == null || k == x.key){
			return x;
		}
		if(k < x.key){
			return treeSerch(x.leftChild, k);
		}else{
			return treeSerch(x.rightChild, k);
		}
	}
	
	public BSTNode iterativeTreeSerch(BSTNode x, int k){
		while(x != null && k != x.key){
			if(k < x.key){
				x = x.leftChild;
			}else{
				x = x.rightChild;
			}
		}
		return x;
	}
	
	public BSTNode treeMinimum(BSTNode x){
		while(x.leftChild != null){
			x = x.leftChild;
		}
		return x;
	}
	
	public BSTNode treeMaxmum(BSTNode x){
		while(x.rightChild != null){
			x = x.rightChild;
		}
		return x;
	}
	
//the successor of a node x is the node with the smallest key greater than x.key
	public BSTNode treeSuccessor(BSTNode x){
		if(x.rightChild != null){
			return treeMinimum(x.rightChild);
		}
		BSTNode y = x.parent;
		while((y != null) && (x == y.rightChild)){
			x = y;
			y = y.parent;
		}
		return y;
	}
	public BSTNode predecessor(BSTNode x){
		if(x.leftChild != null){
			return treeMaxmum(x.leftChild);
		}
		BSTNode y = x.parent;
		while((y != null) && (x == y.leftChild)){
			x = y;
			y = y.parent;
		}
		return y;
	}
	
	public void add(BinarySearchTree T, int key){
		bstNodes.add(new BSTNode(key));
		treeInsert(T, bstNodes.get(bstNodes.size()-1));
	}
	
	public void treeInsert(BinarySearchTree T, BSTNode z){
		BSTNode y = null;
		BSTNode x = T.root;
		while(x != null){
			y = x;
			if(z.key < x.key){
				x = x.leftChild;
			}else{
				x = x.rightChild;
			}
		}
		z.parent = y;
		if(y == null){
			T.root = z; //tree T was empty
		}else if(z.key < y.key) {
			y.leftChild = z;
		}else{
			y.rightChild = z;
		}
	}
	
	public void transplant(BinarySearchTree T, BSTNode u, BSTNode v){
		if(u.parent == null){
			T.root = v;
		}else if(u == u.parent.leftChild){
			u.parent.leftChild = v;
		}else{
			u.parent.rightChild = v;
		}
		if(v != null){
			v.parent = u.parent;
		}
	}
	
	public void treeDelete(BinarySearchTree T, BSTNode z){
		BSTNode y = new BSTNode(0);
		if(z.leftChild == null){
			transplant(T, z, z.rightChild);
		}else if(z.rightChild == null){
			transplant(T, z, z.leftChild);
		}else{
			y = treeMinimum(z.rightChild);
			if(y.parent != z){
				transplant(T, y, y.rightChild);
				y.rightChild = z.rightChild;
				y.rightChild.parent = y;
			}
			transplant(T, z, y);
			y.leftChild = z.leftChild;
			y.leftChild.parent = y;
		}
	}
	
	public static void main(String[] args) {
		BinarySearchTree testTree = new BinarySearchTree();
		testTree.add(testTree, 12);
		testTree.add(testTree, 5);
		testTree.add(testTree, 18);
		testTree.add(testTree, 2);
		testTree.add(testTree, 9);
		testTree.add(testTree, 15);
		testTree.add(testTree, 19);
		testTree.add(testTree, 13);
		testTree.add(testTree, 17);
		testTree.inOrderTreeWalk(testTree.root);
		testTree.treeDelete(testTree, testTree.iterativeTreeSerch(testTree.root, 15));
		//testTree.treeDelete(testTree, testTree.iterativeTreeSerch(testTree.root, 12));
		System.out.println();
		testTree.inOrderTreeWalk(testTree.root);
		System.out.println();
		System.out.println(testTree.treeSuccessor(testTree.treeSerch(testTree.root, 2)).key);
		System.out.println(testTree.treeSuccessor(testTree.treeSerch(testTree.root, 12)).key);
		System.out.println(testTree.predecessor(testTree.treeSerch(testTree.root, 12)).key);
	}

}
